/**
 * 结构体基本用法
 * 
 * struct tag { 
 *   member-list
 *   member-list 
 *   member-list  
 *   ...
 * } variable-list ;
 * 
 * tag 是结构体标签。
 * member-list 是标准的变量定义，比如 int i; 或者 float f，或者其他有效的变量定义。
 * variable-list 结构变量，定义在结构的末尾，最后一个分号之前，您可以指定一个或多个结构变量。
 */

struct Struct_Books{
    char title[50];
    char author[50];
    char subject[50];
    int  book_id;
}
book1 = {"C 语言", "RUNOOB", "编程语言", 123456}, book2;

// 打印结构体数据，给结构体元素赋值
void Struct1()
{
    printf("Struct1:打印结构体数据，给结构体元素赋值\n");
    // 打印 book1 的信息
    printf("title : %s author: %s subject: %s book_id: %d\n", book1.title, book1.author, book1.subject, book1.book_id);

    // 打印 book2 的信息
    printf("title : %s author: %s subject: %s book_id: %d\n", book2.title, book2.author, book2.subject, book2.book_id);

    // 给 book2 赋值
    strcpy(book2.title, "C++ 语言");
    strcpy(book2.author, "RUNOOB");
    strcpy(book2.subject, "编程语言");
    book2.book_id = 456789;

    printf("title : %s author: %s subject: %s book_id: %d\n\n", book2.title, book2.author, book2.subject, book2.book_id);
}

// 声明结构体
void Struct2()
{
    printf("Struct2:声明结构体\n");

    struct Struct_Books book1; // 声明 book1，类型为 Books
    struct Struct_Books book2; // 声明 book2，类型为 Books

    // 给 Book1 各成员赋值 book2 同理
    strcpy(book1.title, "C语言");
    strcpy(book1.author, "RUNOOB");
    strcpy(book1.subject, "编程语言");
    book1.book_id = 123456;

    printf("title : %s author: %s subject: %s book_id: %d\n\n", book1.title, book1.author, book1.subject, book1.book_id);
}

// 数组传递
void Struct3_print(struct Struct_Books book)
{
    printf("title : %s author: %s subject: %s book_id: %d\n\n", book.title, book.author, book.subject, book.book_id);
}

void Struct3()
{
    printf("Struct3:数组传递\n");

    struct Struct_Books book1; // 声明 book1，类型为 Books
    Struct3_print(book1);
}
// 数组传递

// 指向结构体的指针 注意使用 -> 对象访问符号
void Struct4_print(struct Struct_Books *book)
{
    printf("title : %s author: %s subject: %s book_id: %d\n\n", book->title, book->author, book->subject, book->book_id);
}

void Struct4()
{
    printf("Struct4:指向结构体的指针\n");

    struct Struct_Books *p;
    p = &book1;
    Struct4_print(p);
}
// 指向结构体的指针 注意使用 ->

// 自定义数据类型
typedef struct Struct5_tag // 结构体类型
{
    int a;
    float b;
    char c;
    char *d;
} Struct5_Array; // 函数返回类型

Struct5_Array Struct5_Return_Struct(Struct5_Array Array)
{
    Struct5_Array array;
    Array.a = 123;
    Array.b = 1.11;
    Array.c = 99;
    Array.d = "dd";
    return Array;
}

void Struct5_point(Struct5_Array Array)
{
    printf("整数 : %d 小数: %f 字符: %c 字符串: %s\n\n", Array.a, Array.b, Array.c, Array.d);
}

void Struct5()
{
    printf("Struct5:自定义数据类型\n");

    struct Struct5_tag test, test2;

    // 赋值
    test.a = 1;
    test.b = 2.0;
    test.c = 97;
    test.d = "d";

    test2 = Struct5_Return_Struct(test); // 改变值
    Struct5_point(test2); // 打印值
}
// 自定义数据类型

// 单链表的基本运用
typedef struct Struct6_student
{
    int score;
    struct Struct6_student *next;
} Struct6List;

// 打印单链表
void Struct6_print(Struct6List * h)
{
    int i = 0;
    printf("节点个数:%d\n", h->score);
    while (h->next) {
		h = h->next;
        printf("%d:%d  ", ++i, h->score);
	}
    printf("\n");
}

// 创建 n个节点
Struct6List * Struct6_create(int n)
{
    printf("创建单链表：\n");
    
    Struct6List *head, *node, *end; //定义头节点，普通节点，尾节点；  声明结构体变量第一种方式
    
    head = (Struct6List*)malloc(sizeof(Struct6List)); // 申请头结点的内存
    if (head == NULL) {
		printf("分配内存失败！！\n");
		exit(0);
	}

    //注意：尾部节点相当于普通节点最后一个节点 充当的是临时变量的效果
    end = head; // 现在 end 和 head 地址一样
    end -> score = n; // 头结点记录元素个数

    for (int i = 0; i < n; ++i)
    {
        node = (Struct6List*)malloc(sizeof(Struct6List)); // 申请定普通节点的内存
        if (node == NULL) {
            printf("分配内存失败！！\n");
            exit(0);
        }
        node -> score = rand() % 101; // 取0~100的随机数
        end -> next = node; // 头结点的下一个节点指向普通节点 或者 普通节点指向下一个普通节点
        end = node; // end 变为普通节点
    }
    
    end->next = NULL; // 将最后一个普通节点 next置为零 该普通节点变为尾节点
    return head;
}

// 增加指定节点
void Struct6_insert(Struct6List *h, int n)
{
    int i, m;
    Struct6List *node, *end, *tmp;

    node = (Struct6List*)malloc(sizeof(Struct6List)); // 申请普通节点内存
    if (node == NULL) {
		printf("分配内存失败！！\n");
		exit(0);
	}

    end = h;
    node -> score = rand() % 101; // 给新增节点赋值

    // 处理超出范围
    if (n < 1) n = 1;

    // 兼容范围小的(插入节点)
    for (i = 1; i < n; ++i)
        end = end -> next;

    if (h->score < n) {
        end = end -> next; // 在末尾添加节点 需要遍历完所有节点
        node -> next = NULL; // 由于是末尾，需要变为尾部节点
        end -> next = node; // 原先末尾节点连接到新增节点
        m = h->score + 1; // 增加节点位置
    } else {
        tmp = end -> next; // 保存插入位置的节点
        node -> next = tmp; // 新增节点连接插入位置节点
        end -> next = node; // 插入位置前一个节点连接到新增节点
        m = n; // 增加节点位置
    }

    ++h->score; // 节点数量增加
    printf("在第%d位置增加节点：\n", m);
}

// 删除指定节点
void Struct6_delete(Struct6List *h, int n)
{
    struct Struct6_student *tmp, *end; // 声明结构体变量第二种方式
    
    // 处理超出范围
    if (h->score < n)  n = h->score;
    if (n < 1) n = 1;

    printf("删除第%d位置节点\n", n);

    end = h;
    for (int i = n; i > 1; --i)
        end = end -> next; // 找到需要删除节点的前一个节点
    
    tmp = end -> next; // 保存需要删除的节点
    // 如果删除最后一个节点，需要变为尾节点 否则 直接指向下一个节点
    end -> next = h->score == n ? NULL : tmp ->next;
    
    // 释放删除节点的内存
    free(tmp);
    tmp = NULL;
    --h->score; // 节点数量减少
}

// 修改指定节点的值
void Struct6_update(Struct6List * h, int n)
{
    // 处理超出范围
    if (h->score < n)  n = h->score;
    if (n < 1) n = 1;

    printf("修改第%d个节点的值：\n", n);

    for (int i = n; i > 0; --i)
        h = h -> next;
    h -> score = rand() % 101;
}

// 先进先出 移出并获取结构体的第一个节点
Struct6List * Struct6_blpop(Struct6List *h)
{
    Struct6List *tmp = h;
    --h->score; // 节点数量减一

    tmp = tmp->next;
    printf("移出并获取第一节点：%d\n", tmp->score);
    h -> next = tmp->next;
    
    tmp -> next = NULL;
    return tmp;
}

// 先进后出 移出并获取结构体的最后节点
Struct6List * Struct6_brpop(Struct6List *h)
{
    Struct6List *tmp = h, *r;
    --h->score; // 节点数量减一

    // 得到倒数第二节点
    for (int i = h->score; i > 0; --i)
        tmp = tmp->next;
    r = tmp->next; // 保存最后节点

    tmp->next = NULL; // 倒数第二节点变为尾节点
    printf("移出并获取最后节点：%d\n", r->score);
    return r;
}

// 移出并获取结构体的指定节点
Struct6List * Struct6_bzpop(Struct6List *h, int n)
{
    if (n > h->score || n < 1) 
    {
        printf("节点不存在，返回头结点！！\n");
        return h;
    }

    Struct6List *tmp = h, *z;
    --h->score; // 节点数量减一

    // 得到目标节点前一个
    for (int i = 1; i < n; ++i)
        tmp = tmp->next;

    z = tmp->next; // 保存目标节点
    tmp->next = z->next; // n-1节点 连接 n+1节点
    z->next = NULL; // 消除连接

    printf("移出并获取第%d节点：%d\n", n, z->score);
    return z;
}

void Struct6()
{
    printf("Struct6:单链表的基本运用\n");
    struct Struct6_student *h, *l, *r, *z; // 注意 switch不能声明结构体
    
    int n;
    char c;

    printf("请输入需要创建的节点个数：");
    scanf("%d", &n);

    // 创建拥有指定节点个数的单链表
    h = Struct6_create(n); // 得到头结点
    Struct6_print(h); // 打印单链表

    while (TRUE) {
        printf("\n'i':在指定位置增加节点 'd':删除指定位置节点 'u':修改指定位置节点 'l':移出并获取第一节点 'r':移出并获取最后节点 'z':移出并获取指定节点 'q':退出操作\n");
        printf("请输入需要执行得操作：");

        getchar(); // 吃掉换行符
        scanf("%c", &c);

        switch (c)
        {
        case 'i':
            printf("请输入需要增加的节点位置：");
            getchar();
            scanf("%d", &n);

            // 增加指定单链表的值
            Struct6_insert(h, n); 
            Struct6_print(h); // 打印单链表
            break;

        case 'd':
            printf("请输入需要删除的节点位置：");
            getchar();
            scanf("%d", &n);

            // 删除指定节点
            Struct6_delete(h, n);
            Struct6_print(h); // 打印单链表
            break;

        case 'u':
            printf("请输入需要修改的节点位置：");
            getchar();
            scanf("%d", &n);

            // 改变对应节点值
            Struct6_update(h, n); 
            Struct6_print(h); // 打印单链表
            break;

        case 'l':
            l = Struct6_blpop(h);

            printf("移出并获取结构体的第一个节点：%d\n", l->score);
            Struct6_print(h); // 打印单链表
            break;

        case 'r':
            r = Struct6_brpop(h);

            printf("移出并获取结构体的最后节点：%d\n", r->score);
            Struct6_print(h); // 打印单链表
            break;

        case 'z':
            printf("请输入需要移出并获取的节点位置：");
            getchar();
            scanf("%d", &n);

            z = Struct6_bzpop(h, n);
            printf("移出并获取结构体的第%d节点：%d\n", n, z->score);
            Struct6_print(h); // 打印单链表
            break;

        case 'q':
            return;

        default:
            printf("输入错误！请重新输入。\n");
            break;
        }
    }
}
// 单链表的基本运用

// 双向链表的基本运用
typedef struct Struct7Tag
{
    int num; // 数据
    struct Struct7Tag *last; // 前驱地址
    struct Struct7Tag *next; // 后驱地址
} Struct7List;

// 顺序遍历双向链表 Struct7List *hne：头地址或者中间地址
void Struct7_print(Struct7List *hne)
{
    printf("顺序打印双向链表(%d)：", hne->num);
    int i = 0;
    while (hne->next)
    {
        hne = hne->next;
        printf("%d:%d  ", ++i, hne->num);
    }
    printf("\n");
}

// 顺序遍历双向链表 Struct7List *hne：头地址或者尾地址或者中间地址
void Struct7_rprint(Struct7List *hne)
{
    printf("逆序打印双向链表：");
    int i = 0;
    while (hne->last)
    {
        printf("%d:%d  ", ++i, hne->num);
        hne = hne->last;
    }
    printf("\n");
}

// 返回自定义数据结构两种方式 1、struct Struct7Tag 2、Struct7List  int n:节点数量
struct Struct7Tag * Struct7_create(int n)
{
    // 声明结构体 两种方式 同上
    struct Struct7Tag * head;
    Struct7List * node, * end;

    // 申请内存 两种方式  同上
    head = (Struct7List*)malloc(sizeof(struct Struct7Tag));
    if (head == NULL) {
		printf("分配内存失败！！\n");
		exit(0);
	}

    end = head; // end 一开始充当临时变量，最后变成尾节点
    head -> num = n; // 头节点num保存节点个数（不包括头节点）
    head -> last = NULL; // 头结点 上一个节点为NULL

    for (int i = 1; i <= n; ++i)
    {
        node = (Struct7List*)malloc(sizeof(Struct7List)); // 为普通节点申请内存 最后一个普通节点变为尾节点
        if (node == NULL) {
            printf("分配内存失败！！\n");
            exit(0);
        }

        node -> num = rand() % 101; // 随机 0~100 的数字
        node -> last = end; // last 指向 上一个节点地址
        end -> next = node; // 上一个节点 next 指向当前节点
        end = node; // end 变为 这个节点
    }

    end -> next = NULL; // 尾节点 next设为NULL
    return head;
}

// 得到头结点
Struct7List * Struct7_getHead(Struct7List * hne)
{
    while (hne -> last)
        hne = hne -> last;
    return hne;
}

// 得到尾节点
Struct7List * Struct7_getEnd(Struct7List * hne)
{
    while (hne -> next)
        hne = hne -> next;
    return hne;
}

// 得到节点个数 
int Struct7_len(Struct7List * hne)
{
    return Struct7_getHead(hne)->num;
}

// 定位到指定位置（最优算法） Struct7List * hne 任意双向节点地址 int n：<0 相对于尾节点n的位置 =0 返回头结点 >0 相对于头结点n的位置
Struct7List * Struct7_position(Struct7List * hne, int n)
{
    printf("定位到双向链表节点位置：%d\n", n);
    Struct7List *re, *head = hne; // 头结点
    int len, now = 0; // 长度 当前位置
    int direction = 0; // 偏移方向 0：头结点顺序 1：当前位置逆序 2：当前位置顺序
    int num; // 偏移位置
    int i; // 普通变量

    while (head->last)
    {
        ++now;
        head = head->last;
    }
    len = head -> num; // 长度

    // 处理特殊情况
    if (n == 0 || n < -len )
        return head;
    if (n > len)
        n = len;

    num = n < 0 ? n + len + 1 : n; // 从头结点开始应该偏移位置
    i = num - now; // 从当前节点开始应该偏移位置 >0 顺序 <0 逆序

    if (num > abs(i)) {
        if (i < 0) {
            num = -i;
            direction = 1; // 当前节点逆序
        } else {
            num = i;
            direction = 2; // 当前节点顺序
        }
    }

    switch (direction)
    {
        case 0: // 头结点顺序
            re = head;
            for (i = num; i > 0; --i)
                re = re->next;
            break;

        case 1: // 当前节点逆序
            re = hne;
            for (i = num; i > 0; --i)
                re = re->last;
            break;

        case 2: // 当前节点顺序
            re = hne;
            for (i = num; i > 0; --i)
                re = re->next;
            break;
    }
    
    // 测试算法 开启
    // char *tip[] = {"头结点顺序", "当前节点逆序", "当前节点顺序"};
    // printf("%s%d单位\n", tip[direction], num, n);

    return re;
}

// 插入节点 return 1：成功 0：失败 int n：<0 相对于尾节点n的位置 =0 返回头结点 >0 相对于头结点n的位置
int Struct7_insert(Struct7List *hne, int n)
{
    Struct7List *node, *pos;
    node = (Struct7List*)malloc(sizeof(Struct7List)); // 为新增节点申请内存
    if (node == NULL)
    {
        printf("分配内存失败！！\n");
        return 0;
    }

    pos = Struct7_position(hne, n); // 得到 第n节点地址

    if (pos -> last == NULL)
        pos = pos -> next;

    node -> num = rand() % 101; // 0~100 随机数
    node -> next = pos; // 新增节点下一节点 等于 第n节点地址
    node -> last = pos -> last; // 新增节点前驱节点 等于 第n节点前驱节点

    pos->last = node; // 第n节点前驱节点 等于 新增节点地址

    pos = node -> last; // 得到第n-1节点地址
    pos -> next = node; // n-1节点的下一节点地址 等于 新增节点地址

    // 节点数量加一
    pos = Struct7_getHead(hne);
    ++pos -> num;

    printf("在第%d位置插入节点:%d\n", n, node->num);
    return 1;
}

// 删除节点 return 1：成功 0：失败 int n：<0 相对于尾节点n的位置 =0 返回头结点 >0 相对于头结点n的位置
int Struct7_delete(Struct7List *hne, int n)
{
    Struct7List *pos = Struct7_position(hne, n), *node;
    if (pos -> last == NULL) 
        pos = pos -> next;
    
    printf("删除第%d节点：%d\n", n, pos->num);

    node = pos -> next; // 得到n+1节点
    node -> last = pos -> last; 

    node = pos -> last; // 得到n-1节点
    node -> next = pos -> next;

    free(pos); //释放内存
    pos = NULL;
    
    // 节点数减一
    node = Struct7_getHead(hne);
    --node -> num;
    return 1;
}

// 移出对应节点 return 1：成功 0：失败 int n：<0 相对于尾节点n的位置 =0 返回头结点 >0 相对于头结点n的位置
int Struct7_move(Struct7List *pos)
{
    Struct7List *node;

    // 节点数减一
    node = Struct7_getHead(pos);
    --node -> num;

    printf("移出节点：%d\n", pos->num);

    if (pos -> next) {
        node = pos -> next; // 得到n+1节点
        node -> last = pos -> last; 
    }
    
    if (pos -> last) {
        node = pos -> last; // 得到n-1节点
        node -> next = pos -> next;
    }
    
    pos -> last = NULL;
    pos -> next = NULL;
    return 1;
}

// 修改节点 return 1：成功 0：失败 int n：修改位置
int Struct7_update(Struct7List *hne, int n)
{
    Struct7List *pos = Struct7_position(hne, n), *node;
    if (pos -> last == NULL)
        pos = pos -> next;

    pos -> num = rand() % 101; // 重新赋值
    printf("修改第%d节点：%d\n", n, pos -> num);
    return 1;
}

// 移出并获取第一节点 Struct7List * hne：头结点或者中间节点或者尾节点
Struct7List * Struct7_blpop(Struct7List * hne)
{
    Struct7List *pos = Struct7_position(hne, 1); // 得到第一节点
    printf("移出并获取第一节点:%d\n", pos -> num);
    Struct7_move(pos); // 移出对应节点
    return pos;
}

// 移出并获取最后节点
Struct7List * Struct7_brpop(Struct7List * hne)
{
    Struct7List *pos = Struct7_getEnd(hne); // 得到尾节点
    printf("移出并获取尾节点:%d\n", pos -> num);
    Struct7_move(pos); // 移出对应节点
    return pos;
}

// 移出并获取指定节点
Struct7List * Struct7_bzpop(Struct7List * hne, int n)
{
    Struct7List *pos = Struct7_position(hne, n); // 得到第n节点
    printf("移出并获取第%d节点:%d\n", n, pos -> num);
    Struct7_move(pos); // 移出对应节点
    return pos;
}

void Struct7()
{
    printf("Struct7:双向链表的基本运用\n");

    Struct7List *head, *node, *end;
    int len, n;
    char c;

    printf("请输入需要创建的节点个数：");
    scanf("%d", &n);
    getchar(); // 吃掉换行符

    head = Struct7_create(n); // 创建n个节点，返回头结点
    Struct7_print(head); // 顺序打印双向链表

    end = Struct7_getEnd(head); // 得到尾节点
    Struct7_rprint(end); // 逆序打印双向链表

    head = Struct7_getHead(end); // 得到头结点
    Struct7_print(head); // 顺序打印双向链表

    len = Struct7_len(end); // 得到节点长度
    printf("双向链表长度：%d\n", len);

    node = Struct7_position(end, -5); // 定位到节点位置 >=0 正向 <0 逆向
    printf("当前双向链表节点的值：%d\n", node->num);
    Struct7_print(node); // 顺序打印双向链表
    Struct7_rprint(node); // 逆序打印双向链表

    while (TRUE) 
    {
         printf("\n'i':在指定位置增加节点 'd':删除指定位置节点 'u':修改指定位置节点 'l':移出并获取第一节点 'r':移出并获取最后节点 'z':移出并获取指定节点 'q':退出操作\n");
        printf("请输入需要执行得操作：");

        scanf("%c", &c);
        getchar(); // 吃掉换行符

        switch (c)
        {
        case 'i':
            printf("请输入需要增加的节点位置：");
            scanf("%d", &n);
            getchar();

            Struct7_insert(head, n); // 在第n位置插入节点
            Struct7_print(head); // 顺序打印双向链表
            break;

        case 'd':
            printf("请输入需要删除的节点位置：");
            scanf("%d", &n);
            getchar();

            Struct7_delete(head, n); // 删除第n位置节点
            Struct7_print(head); // 顺序打印双向链表
            break;

        case 'u':
            printf("请输入需要修改的节点位置：");
            scanf("%d", &n);
            getchar();

            // 改变对应节点值
            Struct7_update(head, n); // 修改第n节点
            Struct7_print(head); // 顺序打印双向链表
            break;

        case 'l':
            Struct7_blpop(head); // 移出并获取第一节点
            Struct7_print(head); // 顺序打印双向链表
            break;

        case 'r':
            Struct7_brpop(head); // 移出并获取最后节点
            Struct7_print(head); // 顺序打印双向链表
            break;

        case 'z':
            printf("请输入需要移出并获取的节点位置：");
            scanf("%d", &n);
            getchar();

            Struct7_bzpop(head, n); // 移出并获取指定节点
            Struct7_print(head); // 顺序打印双向链表
            break;

        case 'q':
            return;

        default:
            printf("输入错误！请重新输入。\n");
            break;
        }
    }
}
// 双向链表的基本运用

void Struct()
{
    // Struct1(); // 打印结构体数据，给结构体元素赋值
    // Struct2(); // 声明结构体
    // Struct3(); // 数组传递
    // Struct4(); // 指向结构体的指针
    // Struct5(); // 自定义数据类型
    // Struct6(); // 单链表的基本运用
    Struct7(); // 双向链表的基本运用
}